class Solution {
    public int integerBreak(int n) {
        int dp[] = new int[n];
        dp[0] = 1;
        for (int i = 2; i <= n; i++) {
            int max = 0;
            for (int j = 1; j < i; j++) {
                int res1 = j * (i - j);
                int res2 = j * (dp[i - j - 1]);
                max = Math.max(Math.max(res1, res2), max);
            }
            dp[i - 1] = max;
        }
        return dp[n - 1];
    }
}